1. Field of the Invention
The present invention relates to a concurrent processing method and system and more particularly to a concurrent processing method and system which are suitable for high speed inference or sorting.
2. Description of the Prior Art
The concurrent processing method and system are a method and system for concurrently executing a plurality of processes for deriving the same processing result from the same data.
With respect to conventional concurrent processing systems, fault tolerant and highly reliable system are well known.
A fault tolerant system is directed to processing data by a main processor group, and concurrently processing the same data with the same algorithm by a sub-processor group, and backing up the processing by the sub-processor group when the main processor group goes down so as to prevent the processing from stopping. It is indicated, for example, in "Fault Tolerant System (McGraw-Hill Books, Ltd., 1986).
A highly reliable system is directed to processing the same data by a plurality of processor groups using the same algorithm and matching results derived by the processor groups so as improve the reliability of the derived results.
A parallel processing system exists wherein a portion of a job is allotted to each processor and accomplished in parallel. In the concurrent processing system, even when one processing is stopped, processing results can be derived by another processing. However, in the parallel processing system, when one processing is stopped, processing results cannot be derived. Therefore, the two systems are different in kind from each other.
Next, conventional matching algorithm will be outlined.
RETE algorithm: The RETE algorithm is an algorithm for converting the rule condition part to a data flow graph which is called a RETE network before execution and for performing matching by sending fact data to this network. The condition to graph conversion is made by assuming each condition comparison as a network node and connecting the nodes for a comparison logical product or by arranging distribution nodes for distributing the fact flow for a logical sum. Comparisons among the comparisons of the rules, which can be shared, hold comparison nodes and a countermeasure for reducing the comparison count is taken. This algorithm matching is started by updating the fact data in the execution phase and carried out by sending the fact data to the network from the route and updating the internal status (past comparison results) of the network. Finally, the fact which reaches the lowest end of the network realizes the corresponding rule. This updating operation (matching phase) is performed by the following procedure. Firstly, the past comparison results in the network relating to the updated fact are deleted. Next, the comparison starts from the route part of tile network at he latest fact value. Each condition comparison which ends under one condition is made. When the comparison is correct, the fact data passes the node and is stored in an internal memory of the network which is called an alpha memory. To make a comparison spanning conditions next, the value is taken out of an alpha memory and the inter-condition comparison is made. This comparison result is stored in each comparison node (beta memory). In this case, the past matching results are stored in each node, so that only values which are newly stored in the alpha memory are compared. When the comparison is correct, the next node connected to the network is compared. When the comparison at each node is not correct, the fact flow is stopped. Finally, the fact which reaches the lowest end of the network realizes the corresponding rule. This matching algorithm reduces the comparison count and realizes high speed matching by (1) sharing of comparison nodes and (2) holding of past stored results as mentioned above.
TREAT algorithm: The above RETE algorithm stores intermediate comparison results in the network. However, when many facts are updated by rule execution, past matching results lose meaning and the cost for updating the held intermediate results increases. The TREAT algorithm has no beta memory and makes all comparisons spanning the conditions every inference cycle.
XC algorithm: The XC algorithm is a method which does not have either a beta memory or an alpha memory. This algorithm is effective particularly when the number of facts is small and many facts are updated every inference cycle.
The object of the parallel processing system is to speed up the processing and reduce the load. Parallel processing systems aimed at high speed inference are indicated, for example, in Bulletin of Information Processing Society of Japan (Vol. 30, No. 4, p. 486-494, 1989) and Japanese Patent Laid-Open No. 1-98026.
It is an object of the fault tolerant system and highly reliable system which are conventional concurrent processing systems to prevent the processing from stopping and improve the reliability of processing results. However, it is not an object to speed up the processing. The actual processing speed is not high.
On the other hand, the parallel processing system can speed up the processing and the speed-up degree depends on the algorithm. FIG. 9 shows the inference speed when the same data is processed in parallel using different inference algorithms by denoting the inference time in the horizontal axis and the inference cycle number in the vertical axis. As shown in FIG. 9, the inference speed varies with the inference algorithm type. However, it also varies with the inference stage in the same inference algorithm. This means that the inference algorithm at the maximum speed varies with the processing contents. In other words, in a parallel processing system using an algorithm, the processing speed is higher than that in other than the parallel processing but whether the speed is a highest one is uncertain.